'''

'''
from functools import cache
from typing import List, Tuple, Optional
from collections import defaultdict, deque
import heapq
import numpy as np

class Solution:

    # 2^a + 3^b + 5^c 是丑数
    def isUgly(self, n: int) -> bool:
        if n <= 0: return False
        while n % 2 == 0:
            n //= 2
        while n % 3 == 0:
            n //= 3
        while n % 5 == 0:
            n //= 5
        return n == 1

    def nthUglyNumber(self, n: int) -> int:
        ugly_numbers = [1]
        i = j = k = 0
        while len(ugly_numbers) < n:
            p1 = ugly_numbers[i] * 2
            p2 = ugly_numbers[j] * 3
            p3 = ugly_numbers[k] * 5
            next_ugly_number = min(p1, p2, p3)
            ugly_numbers.append(next_ugly_number)
            if next_ugly_number == p1:
                i += 1
            if next_ugly_number == p2:
                j += 1
            if next_ugly_number == p3:
                k += 1
        return ugly_numbers[-1]

print(Solution().nthUglyNumber(10))